// Copyright 2011, Vanya Davidenko.
// Кодировка файла: UTF-8. 
package info.iu9.red;



class NfaInterpreter {
  private final class CommandStateVisitor extends AbstractCommandStateVisitor {
    CommandStateVisitor() {
      unvisited_ = newNfaStatesStack();
    }

    void visitStates() {
      reset();
      while ( !unvisited_.isEmpty() && !matched() ) {
        current_state_ = unvisited_.pop();
        state(current_state_.state_id()).accept(this);
      }
    }

    @Override
    protected boolean matched() {
      return matched_state_ != null;
    }
    NfaState matched_state() {
      return matched_state_;
    }

    @Override
    public void visit(final MatchState s) {
      matched_state_ = current_state_;
    }
    @Override
    public void visit(final BeginSaveState s) {
      current_state_.setSubmatchBegin(s.submatch_num(), str_it_.index());
      inc();
    }
    @Override
    public void visit(final EndSaveState s) {
      current_state_.setSubmatchEnd(s.submatch_num(), str_it_.prevIndex());
      inc();
    }

    @Override
    protected void addToResult() {
      // Эта проверка — самая главная строчка всего проекта.
      // Иначе — та же экспонента как и у возвратных.
      if ( threads_regular_states_.push(current_state_.state_id()) ) {
        threads_.push(current_state_);
      }
    }
    @Override
    protected void newThread(final int next_state_id_offset) {
      final int next_state_id = current_state_.state_id()+next_state_id_offset;
      if ( !current_state_.isProcessed(next_state_id) ) {
        final NfaState n = current_state_.clone();
        n.set_state_id(next_state_id);
        unvisited_.push(n);
      }
    }
    @Override
    protected void move(final int next_state_id_offset) {
      final int next_state_id = current_state_.state_id()+next_state_id_offset;
      if ( current_state_.set_state_id(next_state_id) ) {
        unvisited_.push(current_state_);
      }
    }

    private void reset() {
      setStringIterator(str_it_);
      matched_state_ = null;
      unvisited_.swap(threads_);
      threads_.fastClear();
      threads_regular_states_.clear();

      for ( final NfaState s : unvisited_ ) {
        s.clearProcessed();
      }
    }

    private NfaState matched_state_;
    private NfaState current_state_;
    private final Stack<NfaState> unvisited_;
  }

////////////////////////////////////////////////////////////////////////////////

  private final class RegularStateVisitor extends AbstractRegularStateVisitor {
    RegularStateVisitor() {
      result_ = newNfaStatesStack();
    }

    void visitStates() {
      reset();
      while ( !threads_.isEmpty() ) {
        current_state_ = threads_.pop();
        state(current_state_.state_id()).accept(this);
      }
      threads_.swap(result_);
    }

    @Override
    protected void incIf(final boolean condition) {
      if ( condition ) {
        final int next_state_id = current_state_.state_id() + 1;
        final boolean b = current_state_.set_state_id(next_state_id);
        assert b;
        result_.push(current_state_);

        // Добавление не имеет никакого смысла, кроме как проверка.
        assert threads_regular_states_.push(current_state_.state_id());
      }
    }

    private void reset() {
      result_.fastClear();
      threads_regular_states_.clear();
      setStringIterator(str_it_);

      for ( final NfaState s : threads_ ) {
        s.clearProcessed();
      }
    }

    private NfaState current_state_;
    private final Stack<NfaState> result_;
  }

////////////////////////////////////////////////////////////////////////////////

  NfaInterpreter(final FiniteAutomata fa, final int num_submatches) {
    fa_ = fa;
    num_submatches_ = num_submatches;
    str_it_ = new ForwardStringIterator();

    threads_ = newNfaStatesStack();
    threads_regular_states_ = new StateIdSetList(fa_.size());
    cmd_v_ = new CommandStateVisitor();
    reg_v_ = new RegularStateVisitor();
  }


  Submatch[] search(final String string, final int begin, final int end) {
    reset(string, begin, end);

    for ( int c = str_it_.next() ; c != str_it_.EOL ; c = str_it_.next() ) {
      cmd_v_.visitStates();
      reg_v_.visitStates();
      assert !threads_.isEmpty();
    }

    cmd_v_.visitStates();
    assert cmd_v_.matched();
    return makeSubmatchesArray();
  }

  Submatch[] makeSubmatchesArray() {
    final NfaState state = cmd_v_.matched_state();
    final Submatch[] result = new Submatch[num_submatches_];
    for ( int i = 0 ; i != state.num_submatches() ; i++ ) {
      result[i] = state.makeSubmatch(str_it_.string(), i);
    }
    return result;
  }

  private void reset(final String string, final int begin, final int end) {
    threads_.clear();  // полная очистка за линейное время
    threads_.push(new NfaState(0, fa_.size(), num_submatches_));
    str_it_.reset(string, begin, end);
  }


  private State state(final int state_id) {
    return fa_.get(state_id);
  }
  private Stack<NfaState> newNfaStatesStack() {
    return new Stack<NfaState>(fa_.size());
  }


  private final FiniteAutomata fa_;
  private final int num_submatches_;

  private final CommandStateVisitor cmd_v_;
  private final RegularStateVisitor reg_v_;

  private final StringIterator str_it_;
  private final Stack<NfaState> threads_;
  private final StateIdSetList threads_regular_states_;
}
